#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 树状数组

class binary_indexed_tree
{
private:
    vector<ll> d;
    int _n;
    inline int lowbit(int x)
    {
        return x & -x;
    }

public:
    binary_indexed_tree(int n) : d(n + 1, 0), _n(n) {}

    ll query(int x)
    {
        ll ans = 0;
        while (x)
        {
            ans += d[x];
            x -= lowbit(x);
        }
        return ans;
    }

    void add(int x, ll val)
    {
        assert(x != 0);
        while (x <= _n)
        {
            d[x] += val;
            x += lowbit(x);
        }
    }
};